// 生成不重复的随机数数组
function generateRandomArray(size, maxValue) {
    const result = new Set();
    while (result.size < size) {
        result.add(Math.floor(Math.random() * maxValue));
    }
    return Array.from(result);
}

// 找到数组中第k个最小的元素（k从1开始）
function linearTimeSelect(arr, k) {
    if (arr.length <= 5) {
        // 如果数组大小 <= 5，直接使用排序找到第k小元素
        return arr.sort((a, b) => a - b)[k - 1];
    }

    // 将数组分组，每组最多5个元素
    let groups = [];
    for (let i = 0; i < arr.length; i += 5) {
        groups.push(arr.slice(i, i + 5));
    }

    // 计算每个组的中位数
    let medians = groups.map(group => {
        group.sort((a, b) => a - b);
        return group[Math.floor(group.length / 2)];
    });

    // 递归求中位数的中位数
    let pivot = linearTimeSelect(medians, Math.floor(medians.length / 2) + 1);

    // 分割数组
    let left = [];
    let right = [];
    let pivotCount = 0;
    for (let num of arr) {
        if (num < pivot) {
            left.push(num);
        } else if (num > pivot) {
            right.push(num);
        } else {
            pivotCount++;
        }
    }

    // 确定k所在的区域
    if (k <= left.length) {
        return linearTimeSelect(left, k);
    } else if (k > left.length + pivotCount) {
        return linearTimeSelect(right, k - left.length - pivotCount);
    } else {
        return pivot; // 目标是pivot本身
    }
}

// 测试代码
const size = 10000; // 数据规模
const maxValue = 20000; // 随机数最大值

// 生成随机数数组
const arr = generateRandomArray(size, maxValue);

// 找到第k小的元素（假设我们找第5000小的元素）
const k = 5000;

// 统计执行时间
console.time("Execution Time");
const result = linearTimeSelect(arr, k);
console.timeEnd("Execution Time");

console.log(`第 ${k}小的元素是: ${result}`);
